public class Rob {

    public int rob(int[] nums) {
        return process(false, nums, 0);
    }

    public int process(boolean flag, int[] nums, int i) {
        if (i == nums.length) {
            return 0;
        }
        if (flag) {
            return process(false, nums, i + 1);
        } else {
            return Math.max(process(false, nums, i + 1), process(true, nums, i + 1) + nums[i]);
        }
    }

    public int rob1(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[2][n + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < 2; j++) {
                if (j == 0) {
                    dp[j][i] = Math.max(dp[0][i + 1], dp[1][i + 1] + nums[i]);
                } else {
                    dp[j][i] = dp[0][i + 1];
                }
            }
        }
        return dp[0][0];
    }

    public int rob2(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        dp[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            dp[i] = Math.max(dp[i + 1], dp[i + 2] + nums[i]);
        }
        return dp[0];
    }
}
